矩阵中的路径

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param matrix char字符型二维数组 
# @param word string字符串 
# @return bool布尔型
#
class Solution:
    def __init__(self):
        # 记录遍历的四个方向
        self.dir = [[1,0],[-1,0],[0,1],[0,-1]]
    def dfs(self, matrix, word, visited, x, y, m):
        # 越界或者已经访问过的
        if x < 0&nbs***bsp;x >= len(matrix)&nbs***bsp;y < 0&nbs***bsp;y >= len(matrix[0])&nbs***bsp;visited[x][y]&nbs***bsp;(matrix[x][y] != word[m]):
            return False
        # m为记录当前第几个字符
        if m == len(word) - 1:
            return True
        # 标记经过的位置
        visited[x][y] = True    
        # 上下左右四个方向搜索
        for k in range(4):
            if self.dfs(matrix, word, visited, x+self.dir[k][0], y+self.dir[k][1], m+1):
                return True
        # 没有找到，退回上一格
        visited[x][y] = False
        return False
        
    def hasPath(self , matrix: List[List[str]], word: str) -> bool:
        # 处理特殊情况
        if len(matrix) == 0:
            return False
        # 初始化visited bool矩阵
        visited = [[False for i in range(len(matrix[0]))] for j in range(len(matrix))]
        m = 0
        for x in range(len(matrix)):
            for y in range(len(matrix[0])):
                # 通过dfs找到路径
                if self.dfs(matrix, word, visited, x, y, m):
                    return True
        return False
        

回溯就完事了
class Solution:
    def hasPath(self , matrix: List[List[str]], word: str) -> bool:
        # write code here
        m, n = len(matrix), len(matrix[0])        
        dirs = [[0,1],[1,0],[-1,0],[0,-1]]
        def dfs(x, y, idx):
            if idx == len(word):
                return True
            if 0 <= x < m and 0 <= y < n and not vis[x][y] and matrix[x][y] == word[idx]:
                vis[x][y] = True
                ans = False
                for dx, dy in dirs:                    
                    ans |= dfs(x+dx, y+dy, idx+1)
                vis[x][y] = False
                return ans
            return False
        
        for i in range(m):
            for j in range(n):
                vis = [[False] * n for _ in range(m)]
                if dfs(i, j, 0):
                    return True
        return False

class Solution:
    def hasPath(self , matrix: List[List[str]], word: str) -> bool:
        # write code here
        # 看了视频自己写
        m,n=len(matrix),len(matrix[0])
        def dfs(k,i,j):#k是字符串的第几个字符 i，j是第几个格子
            if not 0<=i<m&nbs***bsp;not 0<=j<n&nbs***bsp;word[k]!=matrix[i][j]:# 先把两种特殊情况拿出来
                return False
            if k==len(word)-1:# 把可以结束的情况也拿出来
                return True
            temp=matrix[i][j]
            matrix[i][j]='*'## 这里是为了省内存 所以在替换东西 为了防止在已经走过的路径里边继续瞎跑
            res=dfs(k+1, i-1, j)&nbs***bsp;dfs(k+1, i+1, j)&nbs***bsp;dfs(k+1, i, j-1)&nbs***bsp;dfs(k+1, i, j+1)
            matrix[i][j]=temp
            return res ##就一直判断就行 这里的res只有两种值 要么True 要么False
        for i in range(m):
            for j in range(n):
                if dfs(0, i, j):
                    return True
        return False

class Solution:
    def dfs(self, matrix, colors, i, j, strs, target): 
        if i in range(0, len(matrix[:]))  and j in range(0,len(matrix[0][:])):
            if colors[i][j] == 0:
                if strs + matrix[i][j]== target:
                    return True
                elif target.find(strs + matrix[i][j]) == -1: #这里换成 target.find(matrix[i][j]) == -1 会超时
                    return False
                elif len(strs + matrix[i][j]) > len(target):
                    return False
                else:
                    colors[i][j] = 1
                    is_exits = self.dfs(matrix, colors, i - 1, j, strs + matrix[i][j], target)&nbs***bsp;self.dfs(matrix, colors, i + 1, j, strs+ matrix[i][j], target)&nbs***bsp;\
                self.dfs(matrix, colors, i, j - 1, strs+ matrix[i][j], target)&nbs***bsp;self.dfs(matrix, colors, i, j + 1,strs+ matrix[i][j], target)
                    colors[i][j] = 0
                    return is_exits
            else:
                return False
        else:
            return False
    def hasPath(self, matrix: List[List[str]], word: str) -> bool:
        m = len(matrix[:])
        n = len(matrix[0][:])        
        for i in range(m):
            for j in range(n):
                colors = [[0 for _ in range(n)] for _ in range(m)]
                if self.dfs(matrix, colors, i, j, "", word):
                    return True
        return False

注意剪枝操作

class Solution:
    def hasPath(self , matrix: List[List[str]], word: str) -> bool:
        # write code here
        a=[0]
        w=len(matrix[0])
        h=len(matrix)
        s=[]
        def check(l):
            b=[]
            for i in l:
                if not(i[0]>=h or i[0]<0 or i[1]>=w or i[1]<0):
                    b.append(i)
            return b
        for i in range(h):#寻找开始位置
            for j in range(w):
                if matrix[i][j]==word[0]:
                    s.append([i,j])
        if not s:
            return False
        def tb(s,x,y):#s当前拼接字符串 ls s的长度
            if a[0]==1:
                return
            s.append(matrix[x][y])
            matrix[x][y]='*'
            if s==list(word):
                a[0]=1
                return
            if s[-1]!=word[len(s)-1]:
                return
            c=check([[x-1,y],[x+1,y],[x,y+1],[x,y-1]])
            for i in c:
                cur=matrix[i[0]][i[1]]
                tb(s,i[0],i[1])
                if a[0]==1:
                    return
                s.pop()
                matrix[i[0]][i[1]]=cur
        for j in s:
            cur=matrix[j[0]][j[1]]
            tb([], j[0], j[1])
            matrix[j[0]][j[1]]=cur
        return a[0]

class Solution:
    def hasPath(self , board: List[List[str]], word: str) -> bool:
        # write code here
        def dfs(i,j,k):
            if (i<0&nbs***bsp;i>len(board)-1)&nbs***bsp;(j<0&nbs***bsp;j>len(board[0])-1):
                return False
            if board[i][j]!=word[k]:
                return False
            if k==len(word)-1:
                return True
            board[i][j]='/'
            res=dfs(i-1,j,k+1)&nbs***bsp;dfs(i+1,j,k+1)&nbs***bsp;dfs(i,j-1,k+1)&nbs***bsp;dfs(i,j+1,k+1)
            board[i][j]=word[k]
            return res

        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j]==word[0]:
                    if dfs(i,j,0):
                        return True
        return False

class Solution:
    def hasPath(self, matrix, word: str) -> bool:
        # write code here
        # 1 遍历找到首字母
        # 2，动态规划 找到符合要求的字符串
        def find_word_len(i, j, word, check):
            x = i
            y = j
            word_list = []
            ans_list = []
            word_len = len(word)

            def test(x, y, word_list, ans_list, word, word_len):
                if y < 0&nbs***bsp;y >= len(matrix[0])&nbs***bsp;x < 0&nbs***bsp;x >= len(matrix)&nbs***bsp;len(word) == 0:
                    return
                if matrix[x][y] == word[0]:
                    if len(word_list) + 1 == word_len:
                        ans_list.append(word_list + [matrix[x][y]])
                        return
                    # 左 y>=0
                    if y >= 1 and not check[x][y - 1]:
                        check[x][y - 1] = 1
                        test(x, y - 1, word_list + [matrix[x][y]], ans_list, word[1:], word_len)
                        check[x][y - 1] = 0
                    # 右 y< len(matrix[0])
                    if y <= len(matrix[0]) - 2 and not check[x][y + 1]:
                        check[x][y + 1] = 1
                        test(x, y + 1, word_list + [matrix[x][y]], ans_list, word[1:], word_len)
                        check[x][y + 1] = 0
                    # 上 x >= 0
                    if x >= 1 and not check[x - 1][y]:
                        check[x - 1][y] = 1
                        test(x - 1, y, word_list + [matrix[x][y]], ans_list, word[1:], word_len)
                        check[x - 1][y] = 0
                    # 下 x < len(matrix)
                    if x <= len(matrix) - 2 and not check[x + 1][y]:
                        check[x + 1][y] = 1
                        test(x + 1, y, word_list + [matrix[x][y]], ans_list, word[1:], word_len)
                        check[x + 1][y] = 0

            test(x, y, word_list, ans_list, word, word_len)
            return ans_list

        n = len(matrix)
        m = len(matrix[0])
        check = [[0 for _ in range(m)] for _ in range(n)]
        if not matrix:
            return False
        for i in range(n):
            for j in range(m):
                if matrix[i][j] == word[0]:
                    ans_list = find_word_len(i, j, word, check)
                    if ans_list:
                        return True
        return False

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param matrix char字符型二维数组 
# @param word string字符串 
# @return bool布尔型
#
class Solution:
    def hasPath(self , matrix , word ):
        if len(word) == 0:
            return False
        else:
            possible_now_point, possible_mat = self.findpath(matrix, word)
            if len(possible_now_point) > 0:
                return True
            else:
                return False
    
    
    def findpath(self , matrix , words):
        if len(words) == 1:
            possible_now_point, possible_mat = self.where(matrix, words)
            return possible_now_point, possible_mat
        
        possible_now_point, possible_mat = self.findpath(matrix, words[1:])
        if len(possible_now_point) == 0:
            return [],[]
        else:
            rowmax, colmax = len(matrix)-1, len(matrix[0])-1
            possible_now_point_new, possible_mat_new = [], []
            for idx,now_point in enumerate(possible_now_point):
                now_mat = possible_mat[idx]
                up_point = [max(now_point[0]-1,0),now_point[1]]
                down_point = [min(now_point[0]+1,rowmax),now_point[1]]
                left_point = [now_point[0],max(now_point[1]-1,0)]
                right_point = [now_point[0],min(now_point[1]+1,colmax)]
                next_points = [up_point,down_point,left_point,right_point]
                for next_point in next_points:
                    if now_mat[next_point[0]][next_point[1]] == words[0]:
                        possible_now_point_new.append(next_point)
                        import copy
                        mat = copy.deepcopy(now_mat)
                        mat[next_point[0]][next_point[1]] = None
                        possible_mat_new.append(mat)
            return possible_now_point_new, possible_mat_new
            
        
    def where(self , matrix , word):
        possible_mat = [] # 记录可能路径
        possible_now_point = [] # 记录可能路径的当前位点
        for row_num in range(len(matrix)):
            if word in matrix[row_num]:
                for col_num, w in enumerate(matrix[row_num]):
                    if word == w:
                        import copy
                        mat = copy.deepcopy(matrix)
                        mat[row_num][col_num] = None
                        possible_mat.append(mat)
                        possible_now_point.append([row_num,col_num])
        return possible_now_point, possible_mat

class Solution:
    def hasPath(self , matrix , word ):
        # write code here
        if len(matrix)==0:
            return False
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if self.backtrack(matrix, word, 0, i, j) :
                    return True
    
    def backtrack(self,matrix, word, n, i, j):
        '''
        n表示当前对比的是word的第n个字符
        i,j表示当前的坐标
        '''
        if n==len(word):
            return True
        if i<0&nbs***bsp;i>=len(matrix)&nbs***bsp;j<0&nbs***bsp;j>=len(matrix[0])&nbs***bsp;matrix[i][j]!=word[n]:
            return False
        temp=matrix[i][j]
        matrix[i][j]='*'
        if self.backtrack(matrix,word,n+1,i+1,j)&nbs***bsp;self.backtrack(matrix,word,n+1,i-1,j)&nbs***bsp;self.backtrack(matrix,word,n+1,i,j+1)&nbs***bsp;self.backtrack(matrix,word,n+1,i,j-1):
            return True
        matrix[i][j]=temp
        return False
        
        

class Solution:
    def findPath(self, matrix, i, j, flag, word, index):
        if index == len(word):
            return True
        if i < 0&nbs***bsp;i == len(matrix)&nbs***bsp;j < 0&nbs***bsp;j == len(matrix[0]):
            return False
        if matrix[i][j] != word[index]&nbs***bsp;flag[i*len(matrix[0])+j]:
            return  False
        flag[i*len(matrix[0])+j] = True
        # 向四周搜索
        if self.findPath(matrix, i-1, j, flag, word, index+1)&nbs***bsp;self.findPath(matrix, i+1, j, flag, word, index+1) \
              &nbs***bsp;self.findPath(matrix, i, j-1, flag, word, index+1)&nbs***bsp;self.findPath(matrix, i, j+1, flag, word, index+1):
            return True
        # 恢复路径
        flag[i * len(matrix[0]) + j] = False
        return False

    def hasPath(self, matrix, word):
        if not matrix&nbs***bsp;not word:
            return False
        width, length = len(matrix), len(matrix[0])
        flag = [False] * (width * length)
        # 字符串下标
        for i in range(width):
            for j in range(length):
                if matrix[i][j] == word[0]:
                    if self.findPath(matrix, i, j, flag, word, 0):
                        return True
        return False

知识点：回溯 DFS
我为淑女月用Python：QwQ

class Solution:
    def dfs(self, matrix, word, i, j, pos):
        if i < 0 or i == len(matrix) or j < 0 or j == len(matrix[0]) or matrix[i][j] != word[pos]:
            return False
        if pos == len(word) - 1:
            return True
        tmp, matrix[i][j] = matrix[i][j], '.'
        ret = self.dfs(matrix, word, i, j - 1, pos + 1) or self.dfs(matrix, word, i, j + 1, pos + 1) \
              or self.dfs(matrix, word, i - 1, j, pos + 1) or self.dfs(matrix, word, i + 1, j, pos + 1)
        matrix[i][j] = tmp
        return ret

    def hasPath(self, matrix, word):
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if self.dfs(matrix, word, i, j, 0): # 如果以matrix[i][j]开头找到了一条路径！
                    return True
        return False